package com.xian.d8_sort_binarysearch;

/**
 * 目标:理解二分搜索的原理并实现。
 *
 * 1、数组的二分查找的实现步骤是什么样的?
 * ●定义变量记录左边和右边位置。
 * ●使用while循环控制查询(条件是左边位置<=右边位置)
 * ·循环内部获取中间元素索引
 * 判断当前要找的元素如果大于中间元素，左边位置=中间索引+1
 * 判断当前要找的元素如果小于中间元素，右边位置=中间索引-1
 * ·判断当前要找的元素如果等于中间元素，返回当前中间元素索引。
 */
public class Test2 {
    public static void main(String[] args) {
        //1、定义数组
        int[] arr = {10, 14, 16, 25, 28, 30, 35, 88, 100};
        System.out.println(binarySearch(arr,35));
        System.out.println(binarySearch(arr,350));

    }

    /**
     * 二分查找算法的实现
     *
     * @param arr  排序好的数组
     * @param data 要查找的数据
     * @return 返回的索引, 如果元素不存在返回-1
     */
    public static int binarySearch(int[] arr, int data) {
        //1、定义左边位置  和  右边位置
        int left = 0;
        int right = arr.length - 1;

        //2、开始循环,折半查询。
        while (left <= right) {
            //取中间索引
            int midIndex = (left + right) / 2;
            //3、判断当前中间位置的元素和要找的元素的大小情况
            if (data > arr[midIndex]) {
                //往右边走,左位置更新为=中间索引+1
                left = midIndex + 1;
            } else if (data < midIndex) {
                //往左边走,右位置更新为=中间索引-1
                right = midIndex - 1;
            } else {
                return midIndex;
            }
        }
        return -1;//查无此元素
    }
}
